package com.example.algorithm.dynamicprogramming;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
 *  '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 *  两个字符串完全匹配才算匹配成功。
 *
 *  说明:
 *  s 可能为空，且只包含从 a-z 的小写字母。
 *  p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
 *
 *  示例 1:
 *  输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 *
 *  示例 2:
 *  输入:
 * s = "aa"
 * p = "*"
 * 输出: true
 * 解释:'*' 可以匹配任意字符串。
 *
 *  示例 3:
 *  输入:
 * s = "cb"
 * p = "?a"
 * 输出: false
 * 解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
 *
 *  示例 4:
 *  输入:
 * s = "adceb"
 * p = "*a*b"
 * 输出: true
 * 解释:第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
 *
 *  示例 5:
 *  输入:
 * s = "acdcb"
 * p = "a*c?b"
 * 输出: false
 *
 */
public class Leetcode44_IsMatch {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("a", "");
        map.put("aab", "*");
        map.put("cb", "?a");
        map.put("adceb", "*a*b");
        map.put("acdcb", "a*c?b");
        map.put("", "");
        map.put("", "****");
        map.put("abcdefgabcdefabc", "abc?*e*f*abc");

        map.forEach((k, v) -> System.out.println(k + "  " + new Solution().isMatch(k, v)));



    }

    static class Solution {

        /**
         * 解法二:贪心 + 回溯
         * 因为'*'可以匹配任意多个字符(0~n)可以贪心的(每次选择匹配最少)进行匹配
         * 即当遇到'*'时依次匹配0个到n个字符,当某种情况下不能成功匹配就进行回溯(增加匹配字符串的个数,重新尝试匹配)
         * 先从尾部开始匹配可以减少回溯
         *
         * 思路:
         * 1. 参数空判断，转为字符数组
         * 2. 双指针逆序尾部比对（结束条件：字符不匹配、遇到*、超过起始）
         * 3. 若p到达起始位置之前，只有s也到达起始位置之前才匹配，否则不匹配
         * 4. 双指针正序头部比对（结束条件：有一个到达右指针、匹配不成功）
         *   4.1 若双字符指针匹配或者p中字符为?，双指针右移
         *   4.2 若p中为*，按照空字符尝试匹配，p指针右移，记录p、s的回溯位置
         *   4.3 若可回溯，则尝试将*多匹配一个字符
         *   4.4 否则匹配不成功，返回
         * 5. 剩余检查：验证p剩余字符是否全为 *，否则匹配不成功
         * @param s
         * @param p
         * @return
         */
        private boolean isMatch2(String s, String p) {
            // 1. 参数空判断，转为字符数组
            if (s == null || s.equals("")) {
                if (p == null || p.equals("")) {
                    return true;
                }
            } else if (p == null || p.equals("")) {
                return false;
            }
            char[] text = s.toCharArray();
            char[] pattern = p.toCharArray();
            int m = text.length;
            int n = pattern.length;
            // 2. 双指针逆序尾部比对（结束条件：字符不匹配、遇到*、超过起始）
            // s: abcdefgabcdefabc
            // p: abc?*e*f*abc
            int sRight = m - 1, pRight = n -1;
            while (pRight >= 0 && sRight >= 0 && pattern[pRight] != '*') {
                if (text[sRight] == pattern[pRight] || pattern[pRight] == '?') {
                    --sRight;
                    --pRight;
                } else { // 尾部不匹配直接返回false
                    return false;
                }
            }
            // 3. 若p到达起始位置之前，只有s也到达起始位置之前才匹配，否则不匹配
            if (pRight == -1) {
                if (sRight == -1)
                    return true;
                else
                    return false;
            }

            // 4. 双指针正序头部比对（结束条件：有一个到达右指针、匹配不成功）
            // s: abcdefgabcdefabc
            // p: abc?*e*f*abc
            int sLeft = 0, pLeft = 0;
            int pBackTrace = -1, sBackTrace = -1;// 用于记录p中出现*时，双指针s、p下标位置方便回溯
            while (sLeft <= sRight && pLeft <= pRight) {
                if ((pattern[pLeft] == text[sLeft]) || pattern[pLeft] == '?') {// 4.1 若p,s匹配,或者p为'?',s、p进行直接后移一位即可
                    ++sLeft;
                    ++pLeft;
                } else if (pattern[pLeft] == '*') {// 4.2 若p中为*，按照空字符尝试匹配，p指针右移，记录p、s的回溯位置
                    pBackTrace = ++pLeft; // 模式串指针右移（相当于* 匹配''),并记录p的回溯位置
                    sBackTrace = sLeft; // 记录s的回溯位置,方便后续贪心回溯
                } else if (sBackTrace != -1 && sBackTrace + 1 <= sRight) {// 4.3 若可回溯，则尝试将*多匹配一个字符
                    ++sBackTrace; // 贪心进行回溯
                    sLeft = sBackTrace;//s在上次尝试的基础上，多走一个字符
                    pLeft = pBackTrace;//p回溯到* 的下一个位置
                } else {// 4.4 否则匹配不成功，返回
                    return false;
                }
            }

            // 5. 剩余检查：验证p剩余字符是否全为 *，否则匹配不成功
            for (int i = pLeft; i <= pRight; i++) {
                if (pattern[i] != '*') {
                    return false;
                }
            }
            return true;
        }

        /**
         * 解法一:动态规划
         *
         * *可以匹配多个字符,存在重复匹配的情况,因此可以考虑使用动态规划(备忘录方式)进行求解
         * 1.原问题与子问题:
         *   s的前缀s[0~i],是否能与p的前缀p[0~j]匹配
         *
         * 2.设置状态:
         *   dp[m+1][n+1] (m=s.length, n=p.length)
         *   dp[i][j]表示s的前缀s[0~i],是否能与p的前缀p[0~j]匹配
         *
         * 3.状态转移方程:
         *   3.1 在本次遍历中当s的字符和p的字符相同或者p的字符为'?'时取决于前一次前缀是否匹配(s,p的索引和dp索引之间相差1),即:
         *      if s[i-1]==p[j - 1] || p[j-1]=='?'   dp[i][j] = dp[i-1][j-1]
         *   3.2 在本次遍历p的字符为'*',由于'*'可以匹配''或者任意字符串,因此先看空的情况是否匹配(dp[i-1][j]),然后再看将s的当前字符匹配(dp[i][j-1]),即
         *      if p[j-1]=='*'   dp[i][j] = dp[i-1][j] || dp[i][j-1]
         *   3.3 其他情况 dp[i][j]=false
         *
         * 4.边界值
         *
         * @param s
         * @param p
         * @return
         */
        private boolean isMatch1(String s, String p) {
            // s或者p为nul或""特殊情况进行处理
            if (s == null || s.equals("")) {
                if (p == null || p.equals("")) {
                    return true;
                }
            } else if (p == null || p.equals("")) {
                return false;
            }

            char[] text = s.toCharArray();
            char[] pattern = p.toCharArray();
            int m = text.length;
            int n = pattern.length;

            boolean[][] dp = new boolean[m + 1][n + 1];// dp[i][j]表示s的前缀s[0~i],是否能与p的前缀p[0~j]匹配)
            // 0列因为除了(0,0)都是false,boolean数组默认就算false所以可以不用写
            dp[0][0] = true;
            // 初始化0行
            for (int i = 1; i <= n; i++) {
                if (pattern[i - 1] == '*') {// '*'可以匹配空串,所以遍历直到找到了p中不是'*',后面的就都是false
                    dp[0][i] = true;
                } else {
                    break;
                }
            }
            // 遍历s,p通过状态转移方程逐行逐列填充剩下的dp值
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (text[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else if (pattern[j - 1] == '*') {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                    }/* else { // 默认就是false
                        dp[i][j] = false;
                    }*/
                }
            }
            return dp[m][n];
        }

        public boolean isMatch(String s, String p) {
            return isMatch2(s, p);
        }
    }
}
